<?php
/**
 * algorithms's name:快速排序
 * time:2015-11-30
 */
$in = [1,3,5,7,9,4,2,5,7,8,5,4,3,2,7,5,8,9,4,2,1,3,5,7,9,4,2,5,7,8,5,4,3,2,7,5,8,9,4,2,1,3,5,7,9,4,2,5,7,8,5,4,3,2,7,5,8,9,4,2,1,3,5,7,9,4,2,5,7,8,5,4,3,2,7,5,8,9,4,2,1,3,5,7,9,4,2,5,7,8,5,4,3,2,7,5,8,9,4,2];
function showtime() {
	echo microtime() . "\n";
}
function showinInfo($in) {
	echo 'data\'s length: ' . count($in) . "\n";
}
function quick_sort($in) {
	if (count($in) <= 1) {
		return $in;
	}
	$left = [];
	$right = [];
	$t = rand(0, count($in)-1);
	for ($i=0; $i < count($in); $i++) {
		if ($i == $t) {
			continue;
		}
		if ($in[$i] < $in[$t]) {
			$left[] = $in[$i];
		} else {
			$right[] = $in[$i];
		}
	}
	$left = quick_sort($left);
	$right = quick_sort($right);
	return array_merge($left, [$in[$t]], $right);
}
showinInfo($in);
showtime();
$out = quick_sort($in);
showtime();
for ($i=0; $i < count($out); $i++) { 
	echo $out[$i].' ';
}
echo "\n";